/*oOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoO*/
/*
Authors: Ram Ovadia 201374022 and Lior Fass 300069705
Project: HW Assignment 4 
Description: This is the header of the module implementing Dijkstra's shprtest path algorithm used in Oiway.  
Reference: an adaptation of the algorithm published on: http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
*/
/*oOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoO*/

#ifndef DJIKSTRA_H
#define DJIKSTRA_H

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

//macro to help abstract a 1d array as a 2d matrix. 
#define DGRAPH(graph,u,v,n) djikstra->graph[u*n + v]

/*
 * struct to hold shortest path algorithm objects 
 * n - number of nodes in the graph. 
 * graph - pointer to adjacency matric representing the roadmap. user allocated.
 * dist - dist[i] will hold the shortest distance from src to i, allocated and freed by module. 
 * sptSet - shortest path tree array, allocated and freed by module.
 * prev - prev[v] will hold the index of the vertex that is previous to v in the shortest path. user allocated. will hold the shortest path.
 */
typedef struct djikstra_t
{
	int n;
	int *graph;
	int *dist;
	int *sptSet;
	int *prev;
} Djikstra;

/*
 * implements Dijkstra's single source shortest path algorithm for a graph represented using adjacency matrix representation
 * 
 * Input:
 * -----
 * graph - holds the adjacency matric representing the graph. 
 * prev - preallocated array of size n to hold the shortest path.     
 * n - number of nodes required in the graph.      
 * src/dest - index of the source/destination node in the graph
 *
 * Output:
 * -----
 * 0 - successful, prev will hold the retraced (forward going) shortest path by node index (ending in -1)
 * 1 - failed. 
 */
int djikstra(int *graph, int *prev, int n, int src, int dest);

#endif // DJIKSTRA_H